package 剑指Offer._0110;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 从尾到头打印链表
 * 算法：链表  递归  栈
 *   使用递归，先递归，再输出
 */
public class _06 {
    int count;
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(5);
        ListNode n2 = new ListNode(4);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(2);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        System.out.println(Arrays.toString(new _06().reversePrint(n1)));
    }

    public int[] reversePrint(ListNode head) {
        // List<Integer> ans = new ArrayList<>();
        int len = 0;
        ListNode tem = head;
        while (tem != null) {
            ++len;
            tem = tem.next;
        }
        int[] ans = new int[len];
        dfs(head, ans);
        return ans;
    }
    public void dfs(ListNode head, int[] ans) {
        if (head == null) {
            return;
        }
        dfs(head.next, ans);
        ans[count++] = head.val;
    }

    public int[] reversePrint_stack(ListNode head) {
        int count = 0;
        Deque<Integer> stack = new LinkedList<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
            ++count;
        }
        int[] ans = new int[count];
        count = 0;
        while (!stack.isEmpty()) ans[count++] = stack.pop();
        return ans;
    }
}
